
#ifdef BUILD_TEST
#include <stdio.h>
#endif

#include <stdlib.h>
#include <string.h>
#include <assert.h>

#include "hash_table.h"
#include "mem_alloc.h"

typedef struct hash_node
{
    struct hash_node * next;
    hash_item val;
} hash_node;

#define ITEM2NODE(item) \
    ((hash_node*)(((char*)item) - ((unsigned int)&(((hash_node*)0)->val))))

struct hash_table
{
    func_hash_cmp hash_cmp;
    func_hash_key hash_key;
    //func_hash_copy hash_copy;
    void * user_data;

    unsigned int item_count;
    unsigned int buckets_size;
    hash_node ** buckets;
};

static hash_node * hash_alloc_node(const void * key, const void * data)
{
    hash_node * node = GET_OBJECT(hash_node);
    if (node) {
        node->next = 0;
        node->val.key = key;
        node->val.data = data;
    }
    return node;
}

static void hash_free_node(hash_node * node)
{
    RELEASE_OBJECT(hash_node, node);
}

#define DEFAULT_SIZE 16

hash_table * hash_table_create(unsigned int init_size,
                               func_hash_cmp hash_cmp,
                               func_hash_key hash_key,
                               //func_hash_copy hash_copy,
                               void * user_data)
{
	hash_table * t= 0;

    if (hash_cmp == 0 || hash_key == 0) {
        return 0;
    }


    t= malloc(sizeof(hash_table));
    if (t) {
        if (init_size == 0) {
            init_size = 16;
        }

        t->buckets = malloc(sizeof(hash_node*) * init_size);
        if( t->buckets==0 ) {
            free(t);
            return 0;
        }

        t->hash_cmp = hash_cmp;
        t->hash_key = hash_key;
        //t->hash_copy = hash_copy;
        t->user_data = user_data;

        t->item_count = 0;
        t->buckets_size = init_size;
        memset(t->buckets, 0, sizeof(struct hash_node*) * init_size);
    }
    return t;
}

void hash_table_free_data_and_destory(hash_table * t,
                                  func_free free_key,
                                  func_free free_data)
{
    unsigned int i;
    for (i = 0; i < t->buckets_size; i++) {
        hash_node * node = t->buckets[i];
        if (node) {
            hash_node * n = node;
            node = node->next;
            if (free_key) free_key((void*)n->val.key);
            if (free_data) free_data((void*)n->val.data);
            hash_free_node(n);
            t->buckets[i] = 0;
        }
    }
    free(t->buckets);
    free(t);
}

void hash_table_destory(hash_table * t)
{
    hash_table_free_data_and_destory(t, 0, 0);
}

void * hash_table_user_data(hash_table * t)
{
    return t->user_data;
}

unsigned int hash_table_size(hash_table * t)
{
    return t->item_count;
}

static hash_node * ht_find(hash_table * t,
                        const char * key,
                        unsigned int ikey,
                        hash_node ** pprev)
{
    hash_node * prev = 0;
    struct hash_node * p = 0;

    assert(t);

    p = t->buckets[ikey];
    while (p) {
        int cmp = t->hash_cmp(key, p->val.key, t->user_data);
        if (cmp == 0) {
            if (pprev) *pprev = prev;
            return p;
        } else if (cmp > 0) {
            prev = p;
            p = p->next;
        } else {
            break;
        }
    }
    return 0;

}

static void ht_resize(hash_table * t);

static void ht_insert(hash_table * t,
                 unsigned int ikey,
                 hash_node * prev,
                 hash_node * cur)
{
    assert(t && ikey < t->buckets_size);
    if (prev) {
        cur->next = prev->next;
        prev->next = cur;
    } else {
        cur->next = t->buckets[ikey];
        t->buckets[ikey] = cur;
    }
    t->item_count++;
    ht_resize(t);
}

static void ht_remove(hash_table * t,
                 unsigned int ikey,
                 hash_node * prev,
                 hash_node * cur)
{
    assert(t && ikey < t->buckets_size);
    if (prev) {
        prev->next = cur->next;
    } else {
        t->buckets[ikey] = cur->next;
    }
    t->item_count--;
}


static void ht_resize(hash_table * t)
{
	unsigned int i = 0;
	hash_node ** old_buckets = 0;
    unsigned int old_buckets_size = 0;
    unsigned int new_buckets_size = 0;

	if (t->item_count <= t->buckets_size) {
        return;
    }


    old_buckets = t->buckets;
    old_buckets_size = t->buckets_size;
    new_buckets_size = old_buckets_size*2;

    t->buckets = malloc(sizeof(hash_node*)*new_buckets_size);
    if (t->buckets == 0) {
        t->buckets = old_buckets;
        return;
    }

    t->buckets_size = new_buckets_size;
    t->item_count = 0;

    //复制
    for (i = 0; i < old_buckets_size; i++) {
        hash_node * node = old_buckets[i];
        while (node) {
            hash_node * prev = 0;
            hash_node * moving = node;
			unsigned int ikey = 0;
            hash_node * cur_pos = 0;
			node = node->next;

            ikey = t->hash_key(moving->val.key, t->user_data) % t->buckets_size;
            cur_pos = ht_find(t, moving->val.key, ikey, &prev);
            assert(cur_pos == 0);
            ht_insert(t, ikey, prev, moving);
        }
    }
    free(old_buckets);
}

hash_item * hash_table_find(hash_table * t, const void * key)
{
	unsigned int ikey;
	hash_node * node;

    if (t == 0) {
        return 0;
    }

    ikey = t->hash_key(key, t->user_data) % t->buckets_size;
    node = ht_find(t, key, ikey, 0);
    if (node) {
        return &(node->val);
    } else {
        return 0;
    }
}

//获取hash表中的项
hash_item * hash_table_find_or_insert(hash_table * t,
                                      const void * key,
                                      int * insert)
{
	unsigned int ikey;
	hash_node * prev;
    hash_node * node;
    
    if (t == 0) {
        if(insert) *insert = 0;
        return 0;
    }

    ikey = t->hash_key(key, t->user_data) % t->buckets_size;

    prev = 0;
    node = ht_find(t, key, ikey, &prev);
    if (node) {
        return &(node->val);
    }

    node = hash_alloc_node(key, 0);
    ht_insert(t, ikey, prev, node);
    if(insert) *insert = 1;
    return &(node->val);
}

hash_item * hash_table_set(struct hash_table * t,
                           const void * key,
                           const void * data)
{
    int insert = 0;
    hash_item * item = hash_table_find_or_insert(t, key, &insert);
    if (insert == 0) {
        item->data = data;
    }
    return item;
}

const void * hash_table_get(struct hash_table * t, const void * key)
{
    hash_item * item = hash_table_find(t, key);
    if (item) {
        return item->data;
    }
    return 0;
}

struct hash_item * hash_table_next(struct hash_table * t,
                                   const hash_item * ite)
{
	unsigned int ikey = 0;

    if (t== 0) {
        return 0;
    }


    if (ite != 0) {
        const hash_node * node = ITEM2NODE(ite);
        if (node->next) {
            hash_node * p = node->next;
            return &(p->val);
        } 
        ikey = t->hash_key(ite->key, t->user_data) % t->buckets_size;

        //next key
        ikey += 1;
    }

    for (; ikey < t->buckets_size; ikey++) {
        if (t->buckets[ikey]) {
            hash_node * p = t->buckets[ikey];
            return &(p->val);
        }
    }
    return 0;
}

void hash_table_remove(struct hash_table * t, const void * key)
{
	unsigned int ikey;

    hash_node * prev;
    hash_node * node;

    if (t == 0) {
        return;
    }

    ikey = t->hash_key(key, t->user_data) % t->buckets_size;

    prev = 0;
    node = ht_find(t, key, ikey, &prev);
    if (node == 0) {
        return;
    }

    ht_remove(t, ikey, prev, node);
    hash_free_node(node);
    return;
}

static int str_hash_cmp(const void *key1, const void *key2, void * user_data)
{
    return strcmp((const char*)key1, (const char*)key2);
}

static unsigned int str_hash_key(const void *key, void * user_data)
{
    unsigned int nhash = 0;
    const char * p = (const char*)key;
    while (*p)  {
        nhash += (nhash<<5) + nhash + *p++;
    }
    return nhash;
}

hash_table * str_hash_table_create(unsigned int size, void * ctx)
{
    return hash_table_create(size, str_hash_cmp, str_hash_key, ctx);
}

void * str_hash_table_set(hash_table * t, const char * key, const void * data)
{
    unsigned int ikey = t->hash_key(key, t->user_data) % t->buckets_size;
    hash_node * prev = 0;
    hash_node * node = ht_find(t, key, ikey, &prev);
	char * nkey;

    if (node) {
        void * r_data = (void*)node->val.data;
        node->val.data = data;
        return r_data;
    }

    // copy key
    nkey = (char*)get_mem((unsigned int)strlen(key)+1);
    strcpy(nkey, key);

    node = hash_alloc_node(nkey, data);
    ht_insert(t, ikey, prev, node);
    return 0;
}

void * str_hash_table_remove(struct hash_table * t, const char * key)
{
    unsigned int ikey = t->hash_key(key, t->user_data) % t->buckets_size;
    hash_node * prev = 0;
    hash_node * node = ht_find(t, key, ikey, &prev);
    void * r_data = 0;
    if (node) {
        r_data = (void*)node->val.data;
        ht_remove(t, ikey, prev, node);
        // free key
        release_mem((void*)node->val.key, (unsigned int)strlen((char*)node->val.key)+1);
        hash_free_node(node);
    }
    return r_data;
}

static void str_key_free(void * p)
{
    char * str = (char*)p;
    release_mem(str, (unsigned int)strlen(str)+1);
}

void str_hash_table_destory(hash_table * t)
{
    hash_table_free_data_and_destory(t, str_key_free, 0);
}

#ifdef BUILD_TEST

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main(int argc, char * argv[])
{
    hash_table * t = hash_table_create(0, str_hash_cmp, str_hash_key, 0);

    int i = 1;
    while (!feof(stdin)) {
        char buff[1024] = {0};
        scanf("%s", buff);
        if (buff[0]==0) {
            continue;
        }

        hash_table_set(t, buff, (void*)i);
        i++;
    }

    hash_item * ite = 0;
    while ((ite=hash_table_next(t, ite)) != 0) {
        printf("value_of_key %s %d\n", (char*)ite->key, (int)ite->data);
    }

    i = 0;
    for(i = 0; i < t->buckets_size; i++) {
        printf("count_of_bucket %4d: ", i);
        int j = 0;
        hash_node * node = t->buckets[i];
        while(node) {
            j++;
            node = node->next;
        }
        printf(" %d\n", j);
    }

    hash_table_destory(t);
    return 0;
}

#endif
